package com.gitee.algorithm.sort;
/*
插入排序：
先分组，分成已排序和未排序两组
注意：
1外层循环的开始：因为你的趟数和未排序的元素第一个元素索引相等，因此趟数从一开始，你的外层循环就可以从一开始。
2内层循环的结束：当判断交换的排序组的倒数第二个就行，因为你是用j和j-1，j不能等于0最大取1.故结束条件为j>0


 */
public class Insertion {
    /*
1.对数组内的元素进行排序
    */
    public static void sort(Comparable[] a) {
        //韩顺平
        for (int i = 1; i < a.length; i++) {//循环遍历未排序元素，趟数
            for (int j = i; j >0; j--) {
                //比较j-1和j处的元素大小，如果大于0，则交换元素，否则退出循环即可。
                if (greater(a[j-1],a[j])) {
                    exch(a,j-1,j);
                }else{
                    break;
                }
            }
        }
        //圣月娥,会报错，可能和包装类有关，但是方法本身没错。不好理解，没有插入的感觉，感觉好像冒泡，用上边。
//        for(int i=1;i<a.length;i++){
//            int j=i-1;
//            int temp=arr[i];
//            for (;j>=0;j--){
//                if(temp<arr[j]){
//                    //后移
//                    arr[j+1]=arr[j];
//                }
//            }
//
//        }
    }



    /*
2.判断v是否大于w
     */
        private static boolean greater (Comparable v, Comparable w){
            return v.compareTo(w) > 0;
        }


    /*
3.交换a数组中，索引i和索引j处的值
     */
        private static void exch (Comparable[]a,int i, int j){
            Comparable temp = a[i];
            a[i] = a[j];
            a[j] = temp;

        }
    }

